The present invention relates to a method and apparatus for decreasing the average time required to retrieve information required by a processor, and more particularly to an apparatus and method for reducing the cache miss penalty in a caching system by generating a speculative physical address in parallel with the translation of a virtual address to a physical address.
One way to increase the performance of a computer system is to decrease the time required to supply a microprocessor with the information it requires Such information, which may include both data and instructions, is typically stored in a memory connected to the microprocessor. To access required information, the microprocessor transmits to the memory an address which corresponds to the physical location in the memory (the "physical address") in which the required information is stored In response, the memory transmits back to the microprocessor the information stored in the memory location designated by the physical address.
The time required to supply a microprocessor with required information may be decreased by decreasing the time lapse between the memory's receipt of the physical address and the transmission of the required information This time lapse is determined by the "speed" of the memory. Unfortunately, the cost of memory increases dramatically with the speed of the memory. Thus, it is rarely practical to use the fastest memory available, especially in systems which require large quantities of memory.
Consequently, it has been discovered that by using a relatively small bank of relatively high-speed memory ("cache memory") as a buffer for a larger bank of slower memory ("system memory"), the average information-request to information-supply speed can be greatly improved. Specifically, in a system having a cache memory (a "cache system"), the microprocessor initially requests information it needs from the cache memory. If the information is stored in the cache memory, the request is said to be a "cache hit" and the information is provided to the microprocessor from the cache memory at the faster rate. If the required information is not stored in the cache memory, the information request is said to be a "cache miss" and the information is retrieved from the system memory at the slower transfer rate. When the information is supplied to the microprocessor from the system memory, a copy of the information is typically stored in the cache memory in anticipation of subsequent requests for the same information. The computational efficiency lost due to a cache miss is referred to herein as the "cache miss penalty."
Many modern computer systems are designed to allow software to address "virtual memory" using "virtual addresses", rather than the actual memory on the system using physical addresses. In a system that supports virtual memory (a "virtual memory system"), the software is allowed to assume that the process it implements may access the system's entire address space, that the memory is contiguous, and that the memory begins at a particular address. Due to these assumptions, the software need not be aware of the actual configuration or usage of the system's memory. Virtual memory systems and the benefits thereof are described in detail by David A. Patterson and John L. Hennessy in Computer Architecture A Quantitative Approach (1990), published by Morgan Kaufmann Publishers, Inc. San Mateo, Calif., pages 432-454.
In virtual memory systems, information must still be stored in the actual system memory. Thus, virtual memory systems must provide a mechanism for translating the virtual addresses generated by the software into physical addresses corresponding to actual memory locations of the system memory. One mechanism commonly used to perform this translation is a translation-lookaside buffer. The concept of translation-lookaside buffers is generally well-known in the art, and is described in detail by David A. Patterson and John L. Hennessy in Computer Architecture A Quantitative Approach (1990), pages 437-438.
Similar to non-virtual memory systems, virtual memory systems may employ caching techniques to decrease the time required to retrieve required information. Virtual memory systems may be designed with cache memories which supply required information in response to physical addresses ("physical-address-indexed caches"), cache memories which supply required information in response to virtual addresses ("virtual-address-indexed caches"), or both. Virtual-address-indexed caches are described in detail by David A. Patterson and John L. Hennessy in Computer Architecture A Quantitative Approach (1990), at page 460.
When information is required in a virtual memory system which employs both a physical-address-indexed cache and a virtual-address-indexed cache, a search for the desired information is performed in the virtual-address-indexed cache while the virtual address is translated to a physical address. If the desired information is not present in the virtual-address-indexed cache, the processor awaits the result of a search for the desired information in the physical-address-indexed cache. Such a search is begun only after the process of determining a physical address is completed. Information retrieval from the physical-address-indexed cache is slower then retrieval from the virtual-address-indexed cache since a translation delay is imposed prior to the search of the physical-address-indexed cache. Thus, a cache miss in the virtual-address-indexed cache results in a cache miss penalty.
In light of the foregoing, in a virtual memory system having a virtual-address-indexed cache and a physical-address-indexed cache, a method and apparatus for reducing the cache miss penalty caused by a cache miss of the virtual-address-indexed cache is clearly desirable Further, it is clearly desirable to provide an apparatus and method for avoiding the logical-to-physical address translation time for at least some cache information retrievals from the physical-address-indexed cache.